|
In computer science, A * (pronounced as "A star" ( listen)) is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between multiple points, called nodes. Noted for its performance and accuracy, it enjoys widespread use. However, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, although other work has found A * to be superior to other approaches.〔 〕 Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first described the algorithm in 1968.〔 〕 It is an extension of Edsger Dijkstra's 1959 algorithm. A * achieves better performance by using heuristics to guide its search. ==Description== A * uses a best-first search and finds a least-cost path from a given initial node to one goal node (out of one or more possible goals). As A * traverses the graph, it builds up a tree of partial paths. The leaves of this tree (called the ''open set'' or ''fringe'') are stored in a priority queue that orders the leaf nodes by a cost function, which combines a heuristic estimate of the cost to reach a goal and the distance traveled from the initial node. Specifically, the cost function is :. Here, is the known cost of getting from the initial node to ; this value is tracked by the algorithm. is a heuristic estimate of the cost to get from to any goal node. For the algorithm to find the actual shortest path, the heuristic function must be admissible, meaning that it never overestimates the actual cost to get to the nearest goal node. The heuristic function is problem-specific and must be provided by the user of the algorithm. For example, in an application like routing, might represent the straight-line distance to the goal, since that is physically the smallest possible distance between any two points. If the heuristic satisfies the additional condition for every edge of the graph (where denotes the length of that edge), then is called monotone, or consistent. In such a case, A * can be implemented more efficiently—roughly speaking, no node needs to be processed more than once (see ''closed set'' below)—and A * is equivalent to running Dijkstra's algorithm with the reduced cost . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「A* search algorithm」の詳細全文を読む スポンサード リンク
|